#include "lista.h"
#include <stdlib.h>
#include <time.h>

typedef struct _nodo {
		void* dato;
		struct _nodo *prox;
} nodo_t;

nodo_t* lista_crear_nodo(void* dato){

	nodo_t* nodo = malloc(sizeof(nodo_t));
	if (nodo == NULL) return NULL;
	
	nodo->dato = dato;
	nodo->prox = NULL;
	return nodo;
}

struct lista{
	nodo_t* prim;
	nodo_t* ult;
	size_t cant;
};

struct lista_iter{
	nodo_t* pos_actual;
	nodo_t* pos_anterior;
};

lista_t *lista_crear()
{
	lista_t* nueva_lista = malloc(sizeof(lista_t));
	if (nueva_lista == NULL) return NULL;

	nueva_lista->prim = nueva_lista->ult = NULL;
	nueva_lista->cant = 0;
	return nueva_lista;
}

void lista_destruir(lista_t *lista, void destruir_dato(void *))
{
	nodo_t* actual;

	while (lista->prim != NULL){
		actual = lista->prim;
		lista->prim = lista->prim->prox;
		if (destruir_dato) destruir_dato(actual->dato);
		free(actual);
		}
	free(lista);	
}

lista_t* lista_clonar(const lista_t* lista)
{	
	lista_t* clon = lista_crear();
	lista_iter_t* iter = lista_iter_crear(lista);

	void* actual;

	while(!lista_iter_al_final(iter))
	{
		actual = lista_iter_ver_actual(iter);
		lista_insertar_ultimo(clon, actual);
		lista_iter_avanzar(iter);
	}
	lista_iter_destruir(iter);
	return clon;
}

bool lista_esta_vacia(const lista_t *lista)
{
	if (lista->cant == 0) return true;
	return false;
}

void *lista_ver_primero(const lista_t *lista)
{
	if (lista_esta_vacia(lista)) return NULL;
	return lista->prim->dato;
}

void *lista_ver_ultimo(const lista_t *lista)
{
	if (lista_esta_vacia(lista)) return NULL;
	return lista->ult->dato;
}

bool lista_insertar_primero(lista_t *lista, void *dato)
{
	nodo_t* nodo = lista_crear_nodo(dato);
	if (nodo == NULL) return false;
	
	nodo_t* nodo_aux;
	
	if (lista_esta_vacia(lista))
	{
		lista->prim = lista->ult = nodo;
	}else
	{
		nodo_aux = lista->prim;
		lista->prim = nodo;
		lista->prim->prox = nodo_aux;
	}
	lista->cant++;
	return true;
}

bool lista_insertar_ultimo(lista_t *lista, void* valor)
{
	nodo_t* nodo = lista_crear_nodo(valor);
	if (nodo == NULL) return false;
	
	if (lista_esta_vacia(lista))
	{
		lista->prim = nodo;
	}else
	{
		lista->ult->prox = nodo;
	}
	lista->ult = nodo;
	lista->cant++;
	return true;
}

void *lista_borrar_primero(lista_t *lista)
{
	if (lista_esta_vacia(lista))return NULL;
	nodo_t* nodo_aux = lista->prim;	//Guardo la referencia al primer elemento
	lista->prim = lista->prim->prox;
	void* dato = nodo_aux->dato;	//Guarda el dato para luego poder eliminar el nodo
	free(nodo_aux);
	lista->cant--;
	return dato;
}

size_t lista_largo(const lista_t *lista)
{
	return lista->cant;
}

lista_iter_t *lista_iter_crear(const lista_t *lista)
{
	lista_iter_t* nuevo_iter = malloc(sizeof(lista_iter_t));
	if (nuevo_iter == NULL) return NULL;
	
	nuevo_iter->pos_actual = lista->prim;
	nuevo_iter->pos_anterior = NULL;
	return nuevo_iter;
}

void *lista_iter_ver_actual(const lista_iter_t *iter)
{
	if (lista_iter_al_final(iter)) return NULL;
	return (iter->pos_actual->dato);
}

bool lista_iter_al_final(const lista_iter_t *iter)
{
	if (iter->pos_actual == NULL) return true;
	return false;
}

void lista_iter_destruir(lista_iter_t *iter)
{
	free(iter);
}

bool lista_iter_avanzar(lista_iter_t *iter)
{
	if (lista_iter_al_final(iter)) return false;
	
	iter->pos_anterior = iter->pos_actual;
	iter->pos_actual = iter->pos_actual->prox;
	return true;
}

bool lista_insertar(lista_t *lista, lista_iter_t *iter, void *dato)
{
	nodo_t* nodo = lista_crear_nodo(dato);
	if (nodo == NULL) return false;
	
	if (lista_esta_vacia(lista))
	{
		lista->prim = lista->ult = nodo;
		iter->pos_actual = lista->prim;
	} else {
		if (iter->pos_anterior == NULL) {
			nodo->prox = iter->pos_actual;
			iter->pos_actual = nodo;
			lista->prim = nodo;
		}else if (lista_iter_al_final(iter))
		{
			iter->pos_anterior->prox = nodo;
			iter->pos_actual = nodo;
			lista->ult = nodo;
		} else {
			iter->pos_anterior->prox = nodo;
			nodo->prox = iter->pos_actual;
			iter->pos_actual = nodo;
		}
	}
	lista->cant++;
	return true;
}

void *lista_borrar(lista_t *lista, lista_iter_t *iter)
{
	if (lista_esta_vacia(lista) || lista_iter_al_final(iter)) return NULL;
	nodo_t* nodo_aux = iter->pos_actual;
	if (iter->pos_anterior == NULL) {
		iter->pos_actual = iter->pos_actual->prox;
		lista->prim = iter->pos_actual;
	}else{
		iter->pos_actual = iter->pos_actual->prox;
		iter->pos_anterior->prox = iter->pos_actual;
		if (lista_iter_al_final(iter)) lista->ult = iter->pos_anterior;
	}
	void* dato = nodo_aux->dato;
	free(nodo_aux);
	lista->cant--;
	return dato;
}

void partir(nodo_t* prim, nodo_t** a, nodo_t** b)
/* Parte una coleccion de punteros enlazados por el medio, recibiendo el puntero al primero. Guarda el inicio de la primeta parte en a, y el inicio de la segunda en b */
{
	nodo_t* lento = prim;
	nodo_t* rapido = prim->prox;

	/* Mientras el nodo rapido avanza 2, el lento avanza 1*/
	while (rapido != NULL){
		rapido = rapido->prox;
		if (rapido != NULL){
			lento = lento->prox;
			rapido = rapido->prox;
		}
	}

	/* Se modifican los punteros para partir la lista */
	*a = prim;
	*b = lento->prox;
	lento->prox = NULL;
}

nodo_t* merge(nodo_t* a, nodo_t* b, bool funcion_comparacion(void* elementoA, void* elementoB))
/* Intercala ordenadamente una coleccion de punteros, devolviendo el menor */
{
  	nodo_t* resultado;

	/* Si a o b son NULL, entonces esa lista se termino */
	if (a == NULL) return b;
	if (b == NULL) return a;

	/* Sino, se avanza en la lista del menor, guardando el primer elemento mas chico para devolverlo */
  	if (funcion_comparacion(a->dato,b->dato))
  	{
	 		resultado = a;
	 		resultado->prox = merge(a->prox, b, funcion_comparacion);
  	} else {
	 		resultado = b;
	 		resultado->prox = merge(a, b->prox, funcion_comparacion);
  	}

  	return resultado;
}

void _mergeSort(nodo_t** prim, bool funcion_comparacion(void* elementoA, void* elementoB))
/* Ordena una coleccion de punteros enlazados por mergeSort. Recibe el puntero al primero */
{
	nodo_t* a;
	nodo_t* b;
	nodo_t* primero = *prim;
	//nodo_t* primero;
 
	/* Caso base -- vacia o un solo elemento */
	if ((primero == NULL) || (primero->prox == NULL))
	{
		return;
	}
 
	/* Partir en la lista a y b */
	partir(primero, &a, &b);
 
  	/* Ordenarlas recursivamente */
  	_mergeSort(&a, funcion_comparacion);
  	_mergeSort(&b, funcion_comparacion);
 
  	/* La lista final sera la union de las 2 */
  	*prim = merge(a, b, funcion_comparacion);
}

void lista_mergeSort(lista_t* lista, bool funcion_comparacion(void* elementoA, void* elementoB))
{
	nodo_t* actual;

	/* Se cambia el primero de la lista por lo que devuelve _mergeSort */
	_mergeSort(&lista->prim, funcion_comparacion);

	/* Se recorre toda la lista para encontrar el ultimo y actualizarlo */
	actual = lista->prim;
	while (actual){
		actual = actual->prox;
	}
	lista->ult = actual;
}

int lista_cantidad(lista_t* lista)
{
	nodo_t* actual;
	int i = 0;

	actual = lista->prim;

	while (actual)
	{
		actual = actual->prox;
		i++;
	}

	return i;
}

void _lista_swap(lista_t* lista, int indice)
{
	nodo_t* actual = lista->prim;

	for (int i = 0; i < indice; i++){
		actual = actual->prox;
	}

	void* aux = lista->prim->dato;		 
	lista->prim->dato = actual->dato;
	actual->dato = aux;
}

void _random_initialize(void)
{
	srand(time(NULL));
}

int _random(int n)
{
	return rand() % (n);
}

void lista_shuffle(lista_t* lista)
{
	int cantidad = lista_cantidad(lista);
	_random_initialize();
	
	for (int i = 0; i < cantidad; i++){
		_lista_swap(lista, _random(cantidad));
	}
}

		
		


